#include <bits/stdc++.h>
#include <stdlib.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
typedef long long ll;
//描述车的结构体
struct node
{
    ll x, y;     //坐标
    bool direct; //方向
    ll len;      //车长
} car[20];
//盘面状态
struct mp
{
    int m[10][10];
};
ll n;                  //盘面大小
ll cnt;                //车的数量
bool car_vis[20];      //统计车数量时标记
bool end_flag;         //找到出口标志
map<string, bool> vis; //记录出现过的盘面状态
string move_s[100000]; //记录移动路径
mp mp_ans;             //记录最终盘面情况
//将盘面转化成字符串便于map映射
string turntype(mp &a)
{
    string s = "";
    for (ll i = 0; i < n; i++)
    {
        for (ll j = 0; j < n; j++)
        {
            s.push_back(a.m[i][j] + 'a');
        }
    }
    return s;
}
//将盘面b拷贝到a中
void mp_copy(mp *a, mp *b)
{
    for (ll i = 0; i < n; i++)
    {
        for (ll j = 0; j < n; j++)
        {
            a->m[i][j] = b->m[i][j];
        }
    }
    return;
}

//打印路径
void print_lujing(ll index)
{
    cout << "红车第" << index << "步到达出口" << endl;
    cout << "以下为移动过程:" << endl;
    for (ll k = 0; k < index; k++)
    {
        cout << "第" << k + 1 << "步:";
        cout << move_s[k] << endl;
    }
    cout << "结束时刻的盘面:" << endl;
    for (ll i = 0; i < n; i++)
    {
        for (ll j = 0; j < n; j++)
        {
            cout << mp_ans.m[i][j] << " ";
        }
        cout << endl;
    }
    return;
}

string turn_id(ll k){
    string temp;
    if(k>9){
        temp.push_back(k/10+'0');
        temp.push_back(k%10+'0');
    }
    else {
        temp.push_back(k+'0');
    }
    return temp;
}

//深度搜索
void dfs(mp &a, ll index)
{
    if (end_flag)
        return;
    vis[turntype(a)] = true;
    // cout<<a.m[2][5]<<endl;
    if (a.m[2][5] == 1)
    {
        mp_copy(&mp_ans, &a);
        print_lujing(index);
        end_flag = true;
        return;
    }
    mp temp;
    for (ll k = 1; k <= cnt; k++)
    {
        //东西方向
        if (car[k].direct)
        {
            ll tx = car[k].x, ty = car[k].y;
            //往西走
            for (ll l = 1; ty - l >= 0; l++)
            {
                if (a.m[tx][ty - l] != 0)
                    break;
                mp_copy(&temp, &a);
                for (ll j = ty - l; j < ty - l + car[k].len; j++)
                    temp.m[tx][j] = k;
                for (ll j = ty - l + car[k].len; j < ty + car[k].len; j++)
                    temp.m[tx][j] = 0;
                if (vis[turntype(temp)])
                    continue;
                string s;
                // s.push_back(k + '0');
                s=s+turn_id(k);
                s = s + "号车 ← *";
                s.push_back('0' + l);
                move_s[index] = s;
                car[k].y = ty - l;
                dfs(temp, index + 1);
                car[k].y = ty;
            }
            //往东走
            for (ll l = 1; ty + car[k].len + l - 1 < n; l++)
            {
                if (a.m[tx][ty + car[k].len + l - 1] != 0)
                    break;
                mp_copy(&temp, &a);
                // temp.m=a.m;
                for (ll j = ty + l; j < ty + car[k].len + l; j++)
                    temp.m[tx][j] = k;
                for (ll j = ty; j < ty + l; j++)
                    temp.m[tx][j] = 0;
                if (vis[turntype(temp)])
                    continue;
                string s;
                // s.push_back(k + '0');
                s=s+turn_id(k);
                s = s + "号车 → *";
                s.push_back('0' + l);
                // s = s + "个格子";
                move_s[index] = s;
                car[k].y = ty + l;
                dfs(temp, index + 1);
                car[k].y = ty;
            }
        }
        //南北方向
        if (!car[k].direct)
        {
            ll tx = car[k].x, ty = car[k].y;
            //往北走
            for (ll l = 1; tx - l >= 0; l++)
            {
                if (a.m[tx - l][ty] != 0)
                    break;
                mp_copy(&temp, &a);
                for (ll i = tx - l; i < tx - l + car[k].len; i++)
                    temp.m[i][ty] = k;
                for (ll i = tx - l + car[k].len; i < tx + car[k].len; i++)
                    temp.m[i][ty] = 0;
                if (vis[turntype(temp)])
                    continue;
                string s;
                // s.push_back(k + '0');
                s=s+turn_id(k);
                s = s + "号车 ↑ *";
                s.push_back('0' + l);
                // s = s + "个格子";
                move_s[index] = s;
                car[k].x = tx - l;
                dfs(temp, index + 1);
                car[k].x = tx;
            }
            //往南走
            for (ll l = 1; tx + car[k].len + l - 1 < n; l++)
            {
                if (a.m[tx + car[k].len + l - 1][ty] != 0)
                    break;
                mp_copy(&temp, &a);
                for (ll i = tx + l; i < tx + car[k].len + l; i++)
                    temp.m[i][ty] = k;
                for (ll i = tx; i < tx + l; i++)
                    temp.m[i][ty] = 0;
                if (vis[turntype(temp)])
                    continue;
                string s;
                // s.push_back(k + '0');
                s=s+turn_id(k);
                s = s + "号车 ↓ *";
                s.push_back('0' + l);
                // s = s + "个格子";
                move_s[index] = s;
                car[k].x = tx + l;
                dfs(temp, index + 1);
                car[k].x = tx;
            }
        }
    }
    return;
}

int main()
{
    IOS;
    // best = 0x3f3f3f3f;
    ifstream file("data.txt");
    mp a;
    n = 6;
    cout << "请输入初始布局：" << endl;
    for (int i = 0; i < n; i++)
    {
        for (ll j = 0; j < n; j++)
        {
            file >> a.m[i][j];
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (ll j = 0; j < n; j++)
        {
            cout << a.m[i][j] << " ";
        }
        cout << endl;
    }
    file.close();
    cnt = 0; //初始车辆为0辆
    memset(car_vis, false, sizeof(car_vis));
    for (ll i = 0; i < n; i++)
    {
        for (ll j = 0; j < n; j++)
        {
            if (a.m[i][j] == 0 || car_vis[a.m[i][j]])
                continue;
            cnt++; //计算车辆的数量
            car_vis[a.m[i][j]] = true;
            car[a.m[i][j]].x = i;
            car[a.m[i][j]].y = j;
            //东西方向
            if (j + 1 < n && a.m[i][j] == a.m[i][j + 1])
            {
                car[a.m[i][j]].direct = true; //true 为东西方向
                car[a.m[i][j]].len = 0;
                for (ll k = j; k < n; k++)
                {
                    if (a.m[i][k] == a.m[i][j])
                        car[a.m[i][j]].len++;
                    else
                        break;
                }
            }
            //南北方向
            if (i + 1 < n && a.m[i][j] == a.m[i + 1][j])
            {
                car[a.m[i][j]].direct = false; //false 为南北方向
                car[a.m[i][j]].len = 0;
                for (ll k = i; k < n; k++)
                {
                    if (a.m[k][j] == a.m[i][j])
                        car[a.m[i][j]].len++;
                    else
                        break;
                }
            }
        }
    }
    // for(ll i=1;i<=cnt;i++){
    //     cout<<i<<":"<<endl;
    //     cout<<car[i].len<<endl;
    //     cout<<car[i].x<<" "<<car[i].y<<endl;
    //     if(car[i].direct)cout<<"东西"<<endl;
    //     else cout<<"南北"<<endl;
    // }
    dfs(a, 0);
    if(!end_flag){
        cout << "该盘面找不到出口" << endl;
    }
    return 0;
}
